#include<iostream>
#include<vector>
#include<deque>
#include<assert.h>
using namespace std;

namespace yangyi
{
    template<class T,class Container = vector<T>,class Compare =std:: less<T>>
    class priority_queue
    {
        public:
        priority_queue()
        {

        }
        template <class InputIterator>
        priority_queue(InputIterator first,InputIterator last)
        {
            while(first!=last)
            {
                _con.push_back(*first);
                ++first;
            }
            for(int i=0;i<(_con.size()-1-1)/2;i--)
            {
                adjsut_down(i);
            }
        }
        //构建一个优先级队列
        template<class InputIterator>
        priority_queue(InputIterator first ,InputIterator last)
        {
            while(first!=last)
            {
                _con.push_back(*first);
                ++first;
            }
            for(int i=(_con.size()-1-1)/2;i--)
            {
                adjsut_down(i);
            }
        }
        template<class InputIterator>
        piority_queue(InputIterator first,InputIterator last)
        {
            while(first!=last)
            {
                _con.push_back(*first);
                first++;
            }
            for(int i=(_con.size()-1-1)/2;i>=0;i--)
            {
                adjust_down(i);
            }
        }
        template<class InputIterator>
        priority_queue(InputIterator first,InputIterator last)
        {
            while(first!=last)
            {
                _con.push_back(*first);
                ++first;
            }
            //采用向下建堆法
            for(int i=(_con.size()-1-1)/2;i>=0;i--)
            {
                adjust_down(i);
            }
        }
        template <class InputIterator>
        priority_queue(InputIterator first,InputIterator last)
        {
            while(first!=last)
            {
                _con,push_back(*first);
                ++first;
            }
            for(int i=(_con.size()-1-1)/2;i>=0;i--)
            {
                adjust_down(i);
            }
        }
        void adjsut_up(size_t child)
        {
            Compare com;
            while(child > 0)
            {
                if(Com(_con[child+1],_con[child]))
                {
                    std::swap(_con[child],_con[child+1]);
                    child=parent;
                    parent=(child-1)/2;
                }
                else
                {
                    break;
                }
            }
        }
        void adjsut_up(size_t child)
        {
            Compare com;
            while(child>0)
            {
                if(Com(_con[child+1],_con[child]))
                {
                    std::swap(_con[child+1],_con[child]);
                    child=parent;
                    parent=(child-1)/2;
                }
                else
                {
                    break;
                }
            }
        }
        void adjust_down(size_t child)
        {
            Compare com;
            while(child>0)
            {
                if(Com(_con[child+1],_con[child]))
                {
                    std::swap(_con[child+1],_con[child]);
                    child=parent;
                    parent=(child-1)/2;
                }
                else
                {
                    break;
                }
            }
        }
        void adjust_down(size_t child)
        {
            Compare com;
            while(child>0)
            {
                if(Com(_con[child],_con[child+1]))
                {
                    std::swap(_con[child+1],_con[child]);
                    child=parent;
                    parent=(child-1)/2;
                }
                else
                {
                    break;
                }
            }
        }
        void push(const T& x)
        {
            _con.push_back(x);
            //尾插以后向上进行建堆
            adjsut_up(_con.size()-1);
        }
        void push(const T& x)
        {
            _con.push_back(x);
            adjust_up(_con.size()-1);
        }
        void push(consnt T& x)
        {
            _con.push_back(x);
            adjust_up(_con.size()-1);
        }
        void push(const T& x)
        {
            _con.push_back(x);
            adjsut_up(_con.size()-1);
        }
        void adjust_down(size_t parent)
        {
            Compare com;
            size_t child=parent*2+1;
            while(child<_con.size())
            {
                if(child+1<_con.size() && com(_con[child],_con[child+1]))
                {
                    child++;
                }
                if(com(_con[parent],_con[child]))
                {
                    std::swap(_con[parent],_con[child]);
                    parent=child;
                    child=parent*2+1;
                }
                else
                {
                    break;
                }
            }
        }
        void adjust_down(size_t parent)
        {
            Compare com;
            child=parent*2+1;
            if(child<_con.size() && com(_con[child+1],_con[child]))
            {
                child++;
            }
            if(com(_con[parent],_con[child]))
            {
                std::swap(_con[parent],_con[child]);
                parent=child;
                child=parent*2+1;
            }
            else
            {
                break;
            }
        }
        void adjust_down(size_t parent)
        {
            Compare com;
            size_t child=parent*2+1;
            if(child<_con.size() && com(_con[child+1],_con[child]))
            {
                child++;
            }
            if(com(_con[child],_con[parent]))
            {
                std::swap(_con[parent],_con[child]);
                parent=child;
                child=parent*2+1;
            }
            else
            {
                break;
            }
        }
        const T& top()
        {
            return _con[0];
        }
        const T& top()
        {
            return _con[0];
        }
        const T& top()
        {
            return _con[0];
        }
        const T& top()
        {
            return _con[0];
        }
        bool empty()const
        {
            return _con.empty();
        }
        bool size()const
        {
            return _con.size();
        }
        void pop()
        {
            std::swap(_con[0],_con[_con.size()-1]);
            _con.pop_back();
            adjust_down(_con[0]);
        }
        void pop()
        {
            std::swap(_con[0],_con[_con.size()-1]);
            _con.pop_back();
            adjust_down(_con[0]);
        }
        void pop()
        {
            std::swap(_con[0],_con[_con.size()-1]);
            _con.pop_back();
            adjust_down(0);
        }
        void adjsut_up(size_t child)
        {
            Compare com;
            size_t parent=(child-1)/2;
            while(child>0)
            {
                if(com(_con[child],_con[parent]))
                {
                    std::swap(_con[parent],_con[child]);
                    parent=child;
                    child=parent*2+1;
                }
                else
                {
                    break;
                }
            }
        }
        private: 
        Container _con;
    };
}

namespace yangyi4
{
    template <class T,class Container = deque<T>>
    class stack
    {
        public:
        void push(const T& x)
        {
            _con.push_back(x);
        }
        void pop()
        {
            _con.pop_back();
        }
        const T& top()const
        {
            return _con.back();
        }
        const T& size()const
        {
            return _con.size();    
        }
        bool empty()
        {
            return _con.empty();
        }
        private:
        Container _con;
    };

    template <class T,class Container = deque<T>>
    class queue
    {
        public:
        void push(const T& x)
        {
            _con.push_back(x);
        }
        void pop()
        {
            _con.pop_front();
        }
        const T& back()const
        {
            return _con.back();
        }
        const T& front()const
        {
            return _con.front();
        }
        const T& size()const
        {
            _con.size();
        }
        bool empty()
        {
            return _con.empty();
        }
        private:
        Container _con;
    };
    
    template<class T,class Container =vector<T>,class Compare=std::less<T>>
    class priority_queue
    {
        public:
        void adjust_up(size_t child)
        {
            Compare com;
            size_t parent=(child-1)/2;
            while(child > 0)
            {
                if(com(_con[parent],_con[child]))
                {
                    std::swap(_con[parent],_con[child]);
                    child=parent;
                    parent=(child-1)/2;
                }
                else
                {
                    break;
                }
            }
        }
        void adjsut_down(size_t parent)
        {
            Compare com;
            size_t child=parent*2+1;
            while(child<_con.size())
            {
                if(child+1<_con.size() && com(_con[child+1],_con[child]))
                {
                    child++;
                }
                if(com(_con[parent],_con[child]))
                {
                    std::swap(_con[child],_con[parent]);
                    parent=child;
                    child=parent*2+1;
                }
                else
                {
                    break;
                }
            }
        }
        template <class InputIterator>
        priority_queue(InputIterator first,InputIterator last)
        {
            while(first!=last)
            {
                _con.push_back(*first);
                first++;    
            }
            for(int i=_con,size();i>=0;i--)
            {
                adjust_up(i);
            }
        }
        void push(const T& x)
        {
            _con.push_back(x);
            adjust_up(_con[_con.size()-1]);
        }
        void pop()
        {
            std::swap(_con[0],_con[_con.size()-1]);
            _con.pop_back();
            adjust_down(_con[0]);
        }
        const T& front()const
        {
            return _con.[0];
        }
        const T& back()const
        {
            return _con.[_con.size()-1];
        }
        const T& size()const
        {
            return _con.size();
        }
        bool empty()
        {
            return _con.empty();
        }
        private:
        Container _con;
    };
}

namespace yangyi4
{
    template <class T>
    class vector
    {
        public:
        typedef T* iterator;
        typedef const T* const_iterator; 
          iterator begin()
          {
            return _start;
          }
          iterator end()
          {
            return _finish;
          }
          const_iterator begin()const
          {
            return _start;
          }
          const_iterator end()const
          {
            return _finish;
          }
          vector()
          :_start(nullptr)
          ,_finish(nullptr)
          ,_end_of_storage(nullptr)
          {

          }
          ~vector()
          {
            delete[] _start;
            _start=_finish=_end_of_storage=nullptr;
          }
          size_t capacity()const
          {
            return _end_of_storage-_start;
          }
          const T& operator[](size_t pos)const{
            return _start[pos];
          }
          T& operator[](size_t pos)
          {
            return _start[pos];
          }
          size_t size()
          {
            return _finish-_start;
          }
          void reserve(size_t n)
          {
            if(n>capacity())
            {
                size_t size=size();
                T* tmp=new T[n];
                if(_start)
                {
                    memcpy(tmp,_start,sizeof(T)*size);
                    delete[] _start;
                }
                _start=tmp;
                _finish=_start+size;
                _end_of_storage=_start+n;
            }
          }
          void reserve(size_t n)
          {
            size_t size=size();
            T* tmp=new T[n];
            if(_start)
            {
                memcpy(tmp,_start,sizeof(T)*size);
                delete[] _start;
            }
            _start=tmp;
            _finish=_start+size;
            _end_of_storage=_start+n;
          }
          void push_back(const T& x)
          {
            if(_finish==_end_of_storage)
            {
                reserve(capaity()==0?4:capacity()*2);
            }
            *_finish=x;
            ++_finish;
          }
          void pop_back()
          {
            assert(finish>_start);
            --_finish;
          }
          void insert(iterator pos,const T& x)
          {
            assert(pos>=_start);
            assert(pos<=_finish);
            if(_finish==_end_of_storage)
            {
                size_t len=pos-_start;
                reserve(capacity()==0?4:capacity()*2);
                pos=len+_start;
            }
            iterator end=_finish-1;
            while(end>=pos)
            {
                *(end+1)=*end;
                --end;
            }
            *pos=x;
            ++_finish;
          }
          iterator erase(iterator pos)
          {
            assert(pos>=_start);
            assert(pos<=_finish);
            iterator begin=pos+1;
            while(begin<_finish)
            {
                *(begin-1)=*begin;
                ++begin;
            }
            --_finish;
            //删除以后是需要返回被删除结点的下一个结点的位置
            return pos;
          }
        private:
        iterator* _start;
        iterator* _finish;
        iterator* end_of_storage;
    };
}

namespace yangyi5
{
    template <class T>
    class vector
    {
        public:
        typedef T* iterator;
        typedef const T* const_iterator;
        vector()
        :_start(nullptr)
        ,_finish(nullptr)
        ,_end_of_storage(nullptr)
        {

        }
        ~vector()
        {
            delete[] _start;
            _start=_finish=_end_of_storage=nullptr;
        }
        const T& size()const
        {
            return _finish-_start;
        }
        const T& capacity()const
        {
            return _end_of_storage-_start;
        }
        void reserve(size_t n)
        {
            if(n>capacity())
            {
                size_t size=size();
                T* tmp=new T[n];
                if(_start)
                {
                    memcpy(tmp,_start,sizeof(T)*size);
                    delete[] _start;
                }
                _start=emp;
                _finish=_start+size;
                _end_of_storage=_start+n;
            }
        }
        void insert(iterator pos,const T& x)
        {
            assert(pos>=_start);
            assert(pos<=_finish);
            if(_finish==_end_of_storage)
            {
                reserve(capacity()==0?4:capacity()*2);
            }
            iterator end=_finish-1;
            while(end>=pos)
            {
                *(end+1)=*end;
                ++end;
            }   
            *pos=x;
            ++_finish;
        }
        iterator erase(iterator pos)
        {
            assert(pos>=_start);
            assert(pos<=_finish);
            iterator begin=pos+1;
            while(begin<size())
            {
                *(begin-1)=*begin;
                ++begin;
            }
            --_finish;
            return pos;
        }
        private:
        iterator _start;
        iterator _finish;
        iterator _end_of_storage;
    };
}

namespace yangyi6
{
    template <class T>
    class vector
    {
        public:
        typedef T* iterator;
        typedef const T* const_iterator;
        
        iterator begin()
        {
            return _start;
        }
        iterator end()
        {
            return _finish;
        }
        const_iterator begin()const
        {
            return _start;
        }
        const_iterator end()const
        {
            return _finish;
        }
        vector()
        :_start(nullptr)
        ,_finish(nullptr)
        ,_end_of_storage(nullptr)
        {

        }
        ~vector()
        {
            delete[] _start;
            _start=_finish=_end_of_storage=nullptr;
        }
        const size_t capacity()const
        {
            return _end_of_storage-_start; 
        }
        const size_t size()const
        {
            return _finish-_start;
        }
        void reserve(size_t n)
        {
            if(n>capacity())
            {
                size_t size=size();
                T* tmp=new T[n];
                if(_start)
                {
                    memcpy(tmp,_start,sizeof(T)*size);
                    delete[] _start;
                }
                _start=tmp;
                _finish=_start+size;
                _end_of_storage=_start+n;
            }
        }
        //插入的问题就涉及到扩容的问题
        void insert(iterator pos,const T& x)
        {
            assert(pos>=_start);
            assert(pos<=_finish);

            iterator end=_finish+1;
            while(end>=pos)
            {
                *(end+1)=*end;
                --end;
            }
            *pos=x;
            ++_finish;
        }
        iterator erase(iterator pos)
        {
            assert(pos>=_start);
            assert(pos<=_finish);

            iterator begin=pos+1;
            while(begin<_finish)
            {
                *(begin-1)=*begin;
                ++begin;
            }
            --_finish;
            return pos;
        }
        void push_back(const T& x)
        {
            if(_finish==_end_of_storage)
            {
                reserve(capacity()==0?4:capacity()*2);
            }
            *_finish=x;
            ++_finish;
        }
        void pop_back()
        {
            assert(_finish>_start);
            --_finish;
        }
        const T& operator[](size_t pos)
        {
            assert(pos<size());
            return _start[pos];
        }
        private:
        iterator _start;
        iterator _finish;
        iterator _end_of_storage;
    };
}

namespace yangyi7
{
    template <class T>
    class vector
    {
        public:
        typedef T* iterator;
        typedef const T* const_iterator;

        vector()
        :_start(nullptr)
        ,_finish(nullptr)
        ,_end_of_storage(nullptr)
        {

        }
        ~vector()
        {
            delete[] _start;
            _start=_finish=_end_of_storage=nullptr;
        }
        const_iterator begin()const
        {
            return _start;
        }
        const_iterator end()const
        {
            return _finish;
        }
        iterator begin()
        {
            return _start;
        }
        iterator end()
        {
            return _finish;
        }
        size_t capacity()const
        {
            return _end_of_storage-_start;
        }
        size_t size()const
        {
            return _finish-_start;
        }
        void reserve(size_t n)
        {
            if(n>capacity())
            {
                size_t size=size();
                T* tmp=new T[n];
                if(_start)
                {
                    memcpy(tmp,_start,sizeof(T)*size);
                    delete[] _start;
                }
                _start=tmp;
                _finish=_start+size;
                _end_of_storage=_start+n;
            }
        }
        
        void insert(iterator pos,const T& x)
        {
            assert(pos>=_start);
            assert(pos<=_finish);
            if(_finish==_end_of_storage)
            {
                reserve(capacity()==0?4:capacity()*2);
            }
            iterator end=_finish;
            while(end>=pos)
            {
                *(end+1)=*end;
                --end;
            }
            *pos=x;
            ++_finish;
        }
        void erase(iterator pos)
        {
            assert(pos>=_start);
            assert(pos<=_finish);

            iterator begin=pos+1;
            while(begin<_finish)
            {
                *(begin-1)=*begin;
                ++begin;
            }
            --_finish;
            return pos;
        }
        const T& operator[](size_t pos)const
        {
            assert(pos<size());
            return _start[pos];
        }
        void push_back(const T& x)
        {
            if(_finish==_end_of_storage)
            {
                reserve(capacity()==0?4:capacity()*2);
            }
            *_finish=x;
            ++_finish;
            //方式简单粗暴
            insert(begin(),x);
        }
        void pop_back()
        {
            assert(_finish>_start);
            --_finish;
            erase(end());
        }
        private:
        iterator _start;
        iterator _finish;
        iterator _end_of_storage;
    };
}
namespace yangyi9
{
    template <class T>
    struct _list_node
    {
        T _data;
        _list_node<T>* _prev;
        _list_node<T>* _next;

        _lsit_node(const T& x=T())
        :_data(x)
        ,_prev(nullptr)
        ,_next(nullptr)
        {

        }
    };
    
    template <class T,class Ref,class Ptr>
    struct __list_iterator
    {
        typedef _list_node<T> Node;
        typedef __list_iterator<T,Ref,Ptr> iterator;

        Node* _node;
        __list_iterator(Node* node)
        :_node(node)
        {
            
        }

        bool operator==(const iterator& it)const
        {
            return _node==it._node;
        }
        bool operator!=(const iterator& it)const
        {
            return _node!=it._node;
        }
        Ref operator*()
        {
            return _node->_data;
        }
        Ptr operator->()
        {
            return &(operator*());
        }
        iterator operator++(int)
        {
            iterator tmp(*this);
            _node=_node->_next;
            return tmp;
        }
        iterator operator++()
        {
            _node=_node->_next;
            return *this;
        }
        iterator& operator--()
        {
            _node=_node->_prev;
            return *this;
        }
        iterator operator--(int)
        {
            iterator tmp(*this);
            _node=_node->_prev;
            return tmp;
        }
    };
    template <class T>
    class list
    {
        typedef _list_node<T> Node;
        public:
        __list_iterator<T,T& ,T*> iterator;
        __list_iterator<T,const T&,const T*> const_iterator; 
        
        const_iterator begin()const
        {
            return const_iterator(_head->_next);
        }
        const_iterator end()const
        {
            return const_iterator(_head);
        }
        list()
        {
            Node* _head=new Node;
            _head=_head->_next;
            _head=_head->_prev;
        }
        void push_back(const T& x)
        {
            Node* newnode=new Node(x);
            Node* tail=_head->_prev;
            tail->_next=newnode;
            newnode->_prev=tail;
            tail->_next=_head;
            _head->_prev=newnode;
        }
        iterator insert(iterator pos,const T& x)
        {
            Node* newnode=new Node(x);
            Node* prev=pos->prev;
            Node* next=pos->prev;
            prev->_next=newnode;
            newnode->_prev=prev;
            newnode->_next=next;
            next->_prev=newnode;

            return iterator(newnode);
        }
        iterator erase(iterator pos)
        {
            Node* cur=pos._node;
            Node* prev=cur->prev;
            Node* next=cur->next;
            prev->_next=next;
            next->_prev=prev;
            delete cur;
            //返回被删除结点的下一个位置
            return iterator(next);
        }
        void push_back(const T& x)
        {
            insert(end(),x);
        }
        void push_front(const T& x)
        {
            insert(begin(),x);
        }
        void pop_front()
        {
            erase(begin());
        }
        void pop_back()
        {
            erase(end());
        }
        private:
        Node* _head;
    };
}

namespace yangyi_3
{
    //因为这里涉及到优先级，所以用堆来表示优先级得大小
    template <class T,class Container = vector<T> ,class Compare = std::less<T>>
    class priority
    {
        public:
        adjust_down(size_t parent)
        {
            Compare com;
            size_t child=parent*2+1;
            while(child<_con.size())
            {
                if(child+1<_con.size() && com(_con[child],_con[child+1]))
                {
                    child++;
                }
                if(com(_con[parent],_con(child)))
                {
                    std::swap(_con[parent],_con[child]);
                    child=parent;
                    parent=child*2+1;
                }
                else
                {
                    break;
                }
            }
        }
        void adjust_up(size_t child)
        {
            Compare com;
            size_t parent=(child-1)/2;
            while(child > 0)
            {
                if(com(_con[parent],_con[child]))
                {
                    std::swap(_con[parent],_con[child]);
                    child=parent;
                    parent=(child-1)/2;
                }
                else
                {
                    break;
                }
            }
        }
        template <class InputIterator>
        priority_queue(InputIterator first,InputIterator last)
        {
            while(first!=last)
            {
                _con.push_back(*first);
                ++first;
            }

            for(int i=_con.size();i>=0;i--)
            {
                adjust_up(i);
            }
        }
        void push(cosnt T& x)
        {
            _con.push_back(x);
            adjust_up(_con[_con.size()-1]);
        }
        void pop()
        {
            std::swap(_con[0],_con[_con.sie()-1]);
            _con.pop_back(_con.size()-1);
            adjust_down(_con[0]);
        }
        const T& back()const
        {
            return _con[_con.size()-1];
        }
        const T& front()const
        {
            return _con[0];
        }
        bool empty()
        {
            return _con.empty();
        }
        size_t size()
        {
            return _con.size();
        }
        private:
        Container _con;
    };
}

namespace yangyi_4
{
    template <class T>
    //这里默认设置为公有的
    struct list_node
    {
        T _data;
        list_node<T>* _prev;
        list_node<T>* _next;

        list_node(const T& x=T())
        :_data(x)
        ,_prev(nullptr)
        ,_next(nullptr)
        {

        }
    };

    template <class T,class Ref, class Ptr>
    struct __list_iterator
    {
        typedef list_node<T> Node;
        typedef __list_iterator<T,Ref,Ptr> iterator;

        Node* _node;
        __list_iterator(Node* node)
        :_node(node);
        {

        }
        Ref operator*()
        {
            return _node->data;
        }
        Ptr operator->()
        {
            return &(operator*());
        }
        bool operator==(const iterator& it)
        {
            return _node==it._node;
        }
        bool operator!=(const iterator& it)
        {
            return _node!=it._node;
        }
        iterator operator++()
        {
            _node=_node->next;
            return *this;
        }
        iterator operator++(int)
        {
            iterator tmp(*this);
            _node=_node->next;
            return tmp;
        }
        iterator operator--()
        {
            _node=_node->next;
            return *this;
        }
        iterator operator--(int)
        {
            iterator tmp(*this);
            _node=_node->prev;
            return tmp;
        }
    };
    template <class T>
    class list
    {
        typedef list_node<T> Node;
        public:
        typedef __list_iterator<T,T& ,T*> iterator;
        typedef __list_iterator<T,const T& ,const T*> const_iterator;

        list()
        {
            Node* _head=new Node;
            _head->_next=_head;
            _head->_prev=_head;
        }
        iterator begin()
        {
            return iterator(_head->_next);
        }
        iterator end()
        {
            return iterator(_head);
        }
        const_iterator begin()const
        {
            return iterator(_head->_next);
        }
        const_iterator end()const
        {
            return iterator(_head);
        }
        iterator insert(iterator pos,const T& x)
        {
            Node* newnode=new Node(x);
            Node* cur=pos._node;
            Node* prev=cur->_prev;

            prev->_next=newnode;
            newnode->_prev=prev;
            newnode->_next=cur;
            cur->_prev=newnode;

            return iterator(newnode);
        }

        iterator erase(iterator pos)
        {
            Node* cur=pos._node;
            Node* prev=cur->_prev;
            Node* next=cur->_next;

            prev->_next=next;
            next->_prev=prev;
            delete cur;
            return iterator(next);
        }
        void push(cosnt T& x)
        {
            insert(end(),x);
        }
        void pop_front()
        {
            erase(begin());
        }
        void pop_back()
        {
            erase(end());
        }
        void push_front(const T& x)
        {
            insert(begin(),x);
        }
        private:
        Node* _head;
    };
}
namespace yangyi0
{
    class Date
    {
        public:
        int GetMonthDay(int year,int month)
        {
            static int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
            int day=days[month];
            if(month==2 && (year%4==0 && year%100!=0)
            || (year%400==0))
            {
                day++;
            }
            return day;
        }
        Date(int year=1900,int month=1,int day=1)
        {
            if(year<1900 || month>12 || month<1
            || day<1 || day>GetMonthDay(year,month))
            {
                cout<<"输入日期非法"<<endl;
            }   
            _year=year;
            _month=month;
            _day=day; 
        }

        Date& operator-=(int day)
        {
            if(day < 0)
            {
                return *this+=-day;
            }
            _day-=day;
            while(day < 0)
            {
                _month--;
                if(_month==0)
                {
                    _month=12;
                    _year--;
                }
                _day+=GetMonthDay(_year,_month);
            }
            return *this;
        }

        Date& operator+=(int day)
        {
            if(day < 0)
            {
                return *this-=-day;
            }
            day+=day;
            while(day>GetMonthDay(_year,_month))
            {
                day-=GetMonthDay(_year,_month);
                _month++;
                if(_month==13)
                {
                    _year++;
                    _month=1;
                }
            }
            return *this;
        }
        Date& operator++()
        {
            *this+=1;
            return *this;
        }
        Date operator++(int)
        {
            Date tmp(*this);
            *this+=1;
            return tmp;
        }
        Date& operator--()
        {
            return *this-=1;
        }
        Date operator--(int)
        {
            Date tmp(*this);
            *this-=1;
            return tmp;
        }
        bool operator==(const Date& d)
        {
            return _year==d._year
            && _month==d._month
            && _day==d._day;
        }
        bool operator!=(const Date& d)
        {
            return !(*this==d);
        }
        bool operator>(const Date& d)
        {
            if(_year > d._year)
            {
                return true;
            }
            else if(_year==d._year)
            {
                if(_month>d._month)
                {
                    return true;
                }
                else if(_month==d._month)
                {
                    if(_day>d._day)
                    {
                        return true;
                    }
                }
            }
            return false;
        }
        bool operator<(const Date& d)
        {
            return !(*this>d || *this==d);
        }
        bool operator>=(const Date& d)
        {
            return !(*this<d);
        }
        bool operator<=(const Date& d)
        {
            return !(*this>d);
        }
        private:
        int _year;
        int _month;
        int _day;
    };
}

#include<string.h>
namespace yangyi6
{
    class string
    {
        public:
        typedef char* iterator;
        typedef const char* const_iterator;

        iterator begin()
        {
            return _str;
        }
        iterator end()
        {
            return _str+_size;
        }
        const_iterator begin()const
        {
            return _str;
        }
        const_iterator end()const
        {
            return _str+_size;
        }
        string()
        :_str(nullptr)
        ,_size(0)
        ,_capacity(0)
        {

        }
        string(const char* str=" ")
        :_str(new char[strlen(str)+1])
        ,_size(strlen(str))
        ,_capacity(strlen(str))
        {
            strcpy(_str,str);
        }

        string(const char* str=" ")
        :_str(new char[strlen(str)+1])
        ,_size(strlen(str))
        ,_capacity(strlen(str))
        {
            //将字符串拷贝过来
            strcpy(_str,str);
        }
        string(const string& s)
        :_str(new char[s._capacity+1])
        ,_size(s._size)
        ,_capacity(s._capacity)
        {
            strcpy(_str,s._str);
        }
        string(const string& s)
        :_str(new char[s._capacity+1])
        ,_size(s._size)
        ,_capacity(s._capacity)
        {
            strcpy(_str,s._str);
        }

        string& operator=(const string& s)
        {
            if(this!=&s)
            {
                char* tmp=new char[s._capacity+1];
                strcpy(tmp,_str);
                delete[] _str;

                _str=tmp;
                _size=s._size;
                _capacity=s._capacity;
            }
            return *this;
        }
        void swap(string& tmp)
        {
            ::swap(_str,tmp._str);
            ::swap(_size,tmp._size);
            ::swap(_capacity,tmp._capacity);
        }
        string(const string& s)
        :_str(nullptr)
        ,_size(0)
        ,_capacity(0)
        {
            string tmp(s._str);
            swap(tmp);
        }
        string(const string& s)
        :_str(nullptr)
        ,_size(0)
        ,_capacity(0)
        {
            string tmp(s._str);
            swap(tmp);
        }
        //拷贝一份备份再赋值
        string(const string& s)
        :_str(nullptr)
        ,_size(0)
        ,_capacity(0)
        {
            string tmp(s._str);
            swap(tmp);
        }
        string& operator=(string& s)
        {
            swap(s);
            return *this;
        }
        string& operator=(const string& s)
        {
            if(this!=&s)
            {
                char* tmp = new char[s._capacity+1];
                strcpy(tmp,s._str);
                delete[] _str;
                //局部变量出了作用域就不再生效了
                _str=tmp;
                _size=s._size;
                _capacity=s._capacity;
            }
        }
        ~string()
        {
            delete[] _str;
            _size=_capacity=0;
        }
        const char* c_str()const
        {
            return _str;
        }
        const char& operator[](size_t pos)const
        {
            assert(pos<_size);
            return _str[pos];
        }
        //有时候颜色的区分也是一个技巧啊
        const char& operator[](size_t pos)const
        {
            assert(pos<_size);
            return _str[pos];
        }
        size_t size()const
        {
            return _size;
        }
        //扩容的时候原来的旧空间需要释放掉
        void reserve(size_t n)
        {
            if(n>_capacity)
            {
                char* tmp=new char[n+1];
                strcpy(tmp,_str);
                delete[] _str;
                _str=tmp;
                _capacity=n;
            }
        }
        void reserve(size_t n)
        {
            if(n>_capacity)
            {
                char* tmp=new char[n+1];
                strcpy(tmp,_str);
                delete[] _str;

                _str=tmp;
                _capacity=n;
            }
        }
        //每次插入的时候必然要先检查容量是否充足
        void push_back(char ch)
        {
            if(_size==_capacity)
            {
                reserve(_capacity==0?4:_capacity*2);
            }
            _str[_size]=ch;
            ++_size;
        }
        void push_back(char ch)
        {
            if(_size==_capacity)
            {
                reserve(_capacity==0?4:_capacity*2);
            }
            _str[_size]=ch;
            _size++;
        }
        void append(const char* str)
        {
            size_t len=strlen(str);
            if(_size+len>_capacity)
            {
                reserve(_size+len);
            }
            strcpy(_str+_size,str);
            _size+=len;
        }
        string& operator+=(char ch)
        {
            push_back(ch);
            return *this;
        }
        string& operator+=(const char* str)
        {
            append(str);
            return *this;
        }
        string& insert(size_t pos,char ch)
        {
            if(_size==_capacity)
            {
                reserve(_capacity==0?4:_capacity*2);
            }
            size_t end=pos+1;
            while(end>pos)
            {
                _str[end]=_str[end-1];
                --end;
            }
            _str[pos]=ch;
            ++_size;
            return *this;
        }
        string& insert(size_t pos,char ch)
        {
            if(_size==_capacity)
            {
                reserve(_capacity==0?4:_capacity*2);
            }
            int end=_size+1;
            while(end>pos)
            {
                _str[end]=_str[end-1];
            }
            _str[pos]=ch;
            ++_size;
            return *this;
        }
        void erase(size_t pos,size_t len=npos)
        {
            assert(pos<_size);
            if(len==npos || pos+len>=_size)
            {
                _str[pos]='\0';
                _size=pos;
            }
            else
            {
                //这里相当于实在进行拼接
                strcpy(_str+_size,_str+pos+len);
                strcpy(_str+_size,_str+pos+len);
                //strcpy(_str+_size,_str+pos+len);
                _size-=len;
            }
        }
        void erase(size_t pos,size_t len=npos)
        {
            assert(pos<_size);
            if(len==npos || pos+len>=_size)
            {
                _str[pos]='\0';
                _size=pos;
            }
            else
            {
                strcpy(_str+pos,_str+pos+len);
                _size-=len;
            }
        }
        const static size_t npos=-1;
        void append(const char* str)
        {
            size_t len=strlen(str);
            if(_size+len>_capacity)
            {
                reserve(_size+len);
            }
            //直接开辟空间以后找到为止将其插入即可
            strcpy(_str+_size,str);
            _size+=len;
        }
        void reserve(size_t n)
        {
            if(n>_capacity)
            {
                char* tmp=new char[n+1];
                strcpy(tmp,_str);
                delete[] _str;

                _str=tmp;
                _capacity=n; 
            }
        }
        ~string()
        {
            delete[] _str;
            _str=nullptr;
            _size=_capacity=0;
        }
        private:
        size_t _capacity;
        size_t _size;
        char* _str;
    };

    //写在类的内部会与this指针抢占首席
    ostream& operator<<(ostream& out,const string& s)
    {
        for(size_t i=0;i<s.size();i++)
        {
            out<<s[i];
        }
        return out;
    }
    
}